<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <!-- 
        解题思路：
        - 拷贝所有节点
        - 拷贝所有的边

        解题步骤：
        - 深度或广度优先遍历所有节点
        - 拷贝所有的节点，存储起来
        - 将拷贝的节点，按照原图的连接方法进行连接
     -->
</head>
<body>
    <script>
        // 深度优先
        var cloneGraph = function(node) {
            if (!node) return;
            const visited = new Map(); // 用map存取原来节点和克隆节点的映射关系
            const dfs = (n) => {
                const nCopy = new Node(n.val); // 以当前节点，新建克隆节点
                visited.set(n, nCopy); // 添加映射关系
                (n.neighbors || []).forEach(ne => { // 遍历当前节点的相邻节点
                    if (!visited.has(ne)) {
                        dfs(ne); // 如果没访问过就深度优先遍历
                    }
                    nCopy.neighbors.push(visited.get(ne)); // 在if之后，此时当前节点的相邻节点已经访问过，可以直接把当前节点的相邻节点复制给克隆节点
                })
            };
            dfs(node);
            return visited.get(node);
        };

        // 广度优先
        var cloneGraph = function(node) {
            if (!node) return;
            const visited = new Map();
            visited.set(node, new Node(node.val));
            const q = [node];
            while(q.length) {
                const n = q.shift();
                (n.neighbors || []).forEach(ne => {
                    if (!visited.has(ne)) {
                        q.push(ne);
                        visited.set(ne, new Node(ne.val));
                    }
                    visited.get(n).neighbors.push(visited.get(ne));
                });
            }
            return visited.get(node);
        };
    </script>
</body>
</html>